package findTargetSumWays

import "fmt"

// 选取数量和最大价值

func findTargetSumWays(nums []int, target int) int {
	num, ok := sum(nums, target)
	if !ok {
		return 0
	}
	// 初始化dp
	dp := make([]int, num+1)
	dp[0] = 1
	for i := 0; i < len(nums); i++ {
		for j := num; j >= nums[i]; j-- {
			dp[j] += dp[j-nums[i]]
			//dp[j] = max(dp[j], dp[j]+dp[j-nums[i]])
			//dp[j] = max(dp[j], dp[j-nums[i]]+nums[i])
		}
		fmt.Println(dp)
	}
	fmt.Println(dp)
	return dp[num]
}

func sum(nums []int, target int) (int, bool) {
	//minN := 0
	total := 0
	for i := 0; i < len(nums); i++ {
		//minN = min(minN, nums[i])
		total += nums[i]
	}
	if total < target || (total+target)%2 == 1 || total+target < 0 {
		return 0, false
	} else {
		return (total + target) / 2, true
	}
}
